//
// Description: 787. K 站中转内最便宜的航班
// Created by Loading on 2021/8/24.
//

#include <bits/stdc++.h>

using namespace std;

int findCheapestPrice(int n, vector<vector<int>> &flights, int src, int dst, int k) {
    // dp[i][j] 表示 从 src 出发，在经过 i 个中转站时，到达 j 的最小花费
    constexpr int INF = 0x3f3f3f3f;
    vector<vector<int>> dp(k + 1, vector<int>(n, INF));

    // 从 src 到 src 花费 0
    dp[0][src] = 0;
    // 0 次中转
    for (auto &flight : flights) {
        if (flight[0] == src) {
            dp[0][flight[1]] = flight[2];
        }
    }
    // 1~k 个中转
    for (int i = 1; i <= k; ++i) {
        for (auto &flight : flights) {
            int trans = flight[0], j = flight[1], cost = flight[2];
            // 状态转移方程，经过 trans 中转与不经过中转花费取小者
            dp[i][j] = min(dp[i][j], dp[i - 1][trans] + cost);
        }
    }

    int res = INF;
    for (int i = 0; i <= k; ++i) {
        res = min(res, dp[i][dst]);
    }
    if (res == INF) {
        res = -1;
    }
    return res;
}

int main() {
    int n = 3;
    vector<vector<int>> flights = {{0, 1, 100},
                                   {1, 2, 100},
                                   {0, 2, 500}};
    int src = 0;
    int dst = 2;
    int k = 1;
    int res = findCheapestPrice(n, flights, src, dst, k);
    cout << res << endl;

    return 0;
}